package com.leetcode.math;

import java.util.ArrayList;
import java.util.List;

public class FindPrimePairs {
    public static void main(String[] args) {

    }

    public List<List<Integer>> findPrimePairs(int n) {
        List<List<Integer>> resList = new ArrayList<>();
        for (int i = 2; i <= n / 2; i++) {
            if (primeOrNot[i] && primeOrNot[n - i]) {
                List<Integer> tmpList = new ArrayList<>();
                tmpList.add(i);
                tmpList.add(n - i);
                resList.add(new ArrayList<>(tmpList));
            }
        }
        return resList;
    }

    static boolean[] primeOrNot = new boolean[1000001];

    static {
        for (int i = 2; i <= 1000000; i++) {
            if (isPrime(i)) {
                primeOrNot[i] = true;
            }
        }
    }

    private static boolean isPrime(int val) {
        if (val < 2) {
            return false;
        }
        for (int i = 2; i <= (int)Math.sqrt(val); i++) {
            if (val % i == 0) {
                return false;
            }
        }
        return true;
    }
}
